/*
 * One example for NOI CSP-J Lesson 8:
 * <https://courses.fmsoft.cn/plzs/noijunior-other-data-structures.html>
 *
 * Author: Vincent Wei
 *  - <https://github.com/VincentWei>
 *  - <https://gitee.com/vincentwei7>
 *
 * Copyright (C) 2025 FMSoft <https://www.fmsoft.cn>.
 * License: GPLv3
 */
#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>

using namespace std;

// 递归计算从第 l 堆开始合并到第 r 堆石子的成本
size_t min_cost_merging_stones(const vector<unsigned>& stones,
        vector<vector<ssize_t>>& memo,
        size_t l, size_t r)
{
    // 递归终止条件
    if (l == r)
        return 0;

    // 是否已经计算过？
    if (memo[l][r] >= 0) {
        return memo[l][r];
    }

    size_t ans = SIZE_MAX;
    size_t sum = 0;                 // 计算从 l 到 r 的石子总数
    for (size_t i = l; i < r; i++) {
        // 以 i 分界，递归计算 l 到 i 的合并成本
        size_t cost = min_cost_merging_stones(stones, memo, l, i);

        // 以 i 分解，递归计算 i + 1 到 r 堆的合并成本
        cost += min_cost_merging_stones(stones, memo, i + 1, r);
        ans = min(ans, cost);

        sum += stones[i];
    }
    sum += stones[r];               // sum 中是合并最后两堆的成本

    // 以 i 分界左右两侧合并后的成本再加上合并这两堆的成本（sum）
    return memo[l][r] = ans + sum;
}

size_t min_cost_merging_stones(const vector<unsigned>& stones,
        vector<vector<ssize_t>>& memo)
{
    return min_cost_merging_stones(stones, memo, 0, stones.size() - 1);
}

int main()
{
    vector<unsigned> stones;
    stones.push_back(1);
    stones.push_back(2);
    stones.push_back(3);

    vector<vector<ssize_t>> memo(stones.size(), vector<ssize_t>(stones.size(), -1));

    size_t min_cost = min_cost_merging_stones(stones, memo);
    cout << min_cost << endl;

    assert(min_cost == 9);
    return 0;
}

